#ifndef __GLF_CONCURRENT_QUEUE_H_INCLUDED__
#define __GLF_CONCURRENT_QUEUE_H_INCLUDED__

#include <glf/concurrent/ticketQueue.h>
#include <glf/concurrent/spscUnboundedQueue.h>
#include <glf/mem/allocator.h>

namespace glf {

//! The concurrent queue is currently implemented on top of multiple single producer, single consumer queue.
/**
 *  The implementation of the SPSC queue is unbounded (a bounded version using a circular buffer
 *  could be implemented if performance is an issue).
 *
 *  In the case of multiple producer, multiple consumer, synchronization method,
 *  such as hashing which requires n spsc queue, where
 *  n = # threads, could also be used to prevent blocking).
 *
 */
template<typename T, typename NodeAllocatorType = Allocator<char> >
class ConcurrentQueue
{
public:
	// Type definitions
	typedef T										ValueType;
	typedef ValueType&								Reference;
	typedef const ValueType&						ConstReference;
public:
	ConcurrentQueue(int concurentAccessCount = 1)
		: m_PushListID(0)
		, m_PopListID(0)
		, m_Size(0)
	{
		m_Lists = new List[concurentAccessCount];
		m_ListCount = concurentAccessCount;
	}

	~ConcurrentQueue()
	{
		delete[] m_Lists;
	}

	inline void Push(ConstReference value) {
		Select(m_PushListID++).Push(value);
		++m_Size;
	}

	//! Try to dequeue (remove at the beginning of the queue) the next element.
	/** It is up to the underlying queue to manage the destruction method.
	 *
	 *  \return true if the element was dequeued correctly, false otherwise.
	 */
	inline bool TryPop(Reference value) {
		int size = m_Size;
		while(size != 0)
		{
			if(size == m_Size.compareAndSwap(size - 1, size))
			{
				// Decrease succeed
				break;
			}
			else
			{
				// Try again
				size = m_Size;
			}
		}

		if(size == 0)
		{
			return false;
		}

		int id = m_PopListID++;
		while(Select(id).TryPop(value) == false);
		return true;
	}

	//! Returns the number of elements in the queue.
	inline size_t Size() {
		return m_Size;
	}

	//! Returns whether the queue is empty, i.e. whether its size is 0.
	inline bool Empty() {
		return m_Size == 0;
	}

protected:
	TicketQueue< T, SPSCUnboundedQueue<T, NodeAllocatorType> >& Select(unsigned int listID)
	{
		return m_Lists[listID % m_ListCount];
	}

	typedef TicketQueue< T, SPSCUnboundedQueue<T, NodeAllocatorType> > List;
	//typedef std::vector< List > Lists;

	List* m_Lists;
	int m_ListCount;
	char cache_line_delimiter_1__[GLF_CACHE_LINE_SIZE];
	Atomic32 m_PushListID;
	char cache_line_delimiter_2__[GLF_CACHE_LINE_SIZE];
	Atomic32 m_PopListID;
	char cache_line_delimiter_3__[GLF_CACHE_LINE_SIZE];
	Atomic32 m_Size;
};

} // namespace glf

#endif // __GLF_CONCURRENT_QUEUE_H_INCLUDED__
